<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 6.0.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/wang-cheng/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/wang-cheng/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/wang-cheng/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/wang-cheng/images/logo.svg" color="#222">

<link rel="stylesheet" href="/wang-cheng/css/main.css">


<link rel="stylesheet" href="/wang-cheng/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"cheng-wang123.gitee.io","root":"/wang-cheng/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
  </script>

  <meta name="description" content="树形dp套路树形套路使用前提: 如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中。 题目；二叉树节点间的最大距离问题 从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫做a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离 经验：这种题一般情况下都会分成两类  根节">
<meta property="og:type" content="article">
<meta property="og:title" content="算法笔记(五)">
<meta property="og:url" content="https://cheng-wang123.gitee.io/wang-cheng/2022/04/05/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%BA%94/index.html">
<meta property="og:site_name" content="诚の博客">
<meta property="og:description" content="树形dp套路树形套路使用前提: 如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中。 题目；二叉树节点间的最大距离问题 从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫做a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离 经验：这种题一般情况下都会分成两类  根节">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2022-04-05T04:53:28.000Z">
<meta property="article:modified_time" content="2022-04-07T09:45:51.552Z">
<meta property="article:author" content="王诚">
<meta property="article:tag" content="左神">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="https://cheng-wang123.gitee.io/wang-cheng/2022/04/05/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%BA%94/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>算法笔记(五) | 诚の博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/wang-cheng/atom.xml" title="诚の博客" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/wang-cheng/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">诚の博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">记录学习中的点点滴滴</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/wang-cheng/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/wang-cheng/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/wang-cheng/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/wang-cheng/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
  </ul>
</nav>




</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://cheng-wang123.gitee.io/wang-cheng/2022/04/05/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%BA%94/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/wang-cheng/images/avatar.gif">
      <meta itemprop="name" content="王诚">
      <meta itemprop="description" content="命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="诚の博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          算法笔记(五)
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2022-04-05 12:53:28" itemprop="dateCreated datePublished" datetime="2022-04-05T12:53:28+08:00">2022-04-05</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2022-04-07 17:45:51" itemprop="dateModified" datetime="2022-04-07T17:45:51+08:00">2022-04-07</time>
              </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h2 id="树形dp套路"><a href="#树形dp套路" class="headerlink" title="树形dp套路"></a><strong>树形dp套路</strong></h2><p>树形套路使用前提:</p>
<p>如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中。</p>
<p>题目；二叉树节点间的最大距离问题</p>
<p>从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫做a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离</p>
<p>经验：这种题一般情况下都会分成两类</p>
<ol>
<li><p>根节点不参与组成最大距离的路径 左边的最大距离maxdistance、右边的最大距离maxdistance</p>
</li>
<li><p>根节点参与组成最大距离的路径  左树的最大高度h+右树最大高度h+1</p>
</li>
</ol>
<figure class="highlight pgsql"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">public</span> static <span class="type">int</span> maxDistance(Node node)&#123;</span><br><span class="line">    <span class="keyword">return</span> process(node).maxDistance;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">public</span> static <span class="keyword">class</span> <span class="keyword">Info</span> &#123;</span><br><span class="line">    <span class="built_in">public</span> <span class="type">int</span> maxDistance;</span><br><span class="line">    <span class="built_in">public</span> <span class="type">int</span> height;</span><br><span class="line">    <span class="built_in">public</span> <span class="keyword">Info</span>(<span class="type">int</span> m, <span class="type">int</span> h) &#123;</span><br><span class="line">        maxDistance = m;</span><br><span class="line">        height = h;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">public</span> static <span class="keyword">Info</span> process(Node x) &#123;</span><br><span class="line">    <span class="keyword">if</span> (x == <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">new</span> <span class="keyword">Info</span>(<span class="number">0</span>, <span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">Info</span> leftInfo = process(x.left);</span><br><span class="line">    <span class="keyword">Info</span> rightInfo = process(x.right);</span><br><span class="line">    <span class="type">int</span> height = Math.max(leftInfo.height, rightInfo.height) + <span class="number">1</span>;</span><br><span class="line">    <span class="type">int</span> p1 = leftInfo.maxDistance;</span><br><span class="line">    <span class="type">int</span> p2 = rightInfo.maxDistance;</span><br><span class="line">    <span class="type">int</span> p3 = leftInfo.height + rightInfo.height + <span class="number">1</span>;</span><br><span class="line">    <span class="type">int</span> maxDistance = Math.max(Math.max(p1, p2), p3);</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">new</span> <span class="keyword">Info</span>(maxDistance, height);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>树形dp套路第一步:</p>
<p>以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的</p>
<p>树形dp套路第二步:</p>
<p>根据第一步的可能性分析，列出所有需要的信息</p>
<p>树形dp套路第三步:</p>
<p>合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构</p>
<p>树形dp套路第四步:</p>
<p>设计递归函数，递归函数是处理以X为头节点的情况下的答案。包括设计递归的basecase，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构</p>
<h2 id="Morris遍历"><a href="#Morris遍历" class="headerlink" title="Morris遍历"></a><strong>Morris遍历</strong></h2><p>一种遍历二叉树的方式，并且时间复杂度O(N),额外空间复杂度O(1)。</p>
<p>通过利用原树中大量空闲指针的方式，达到节省空间的目的</p>
<h3 id="Morris遍历细节"><a href="#Morris遍历细节" class="headerlink" title="Morris遍历细节"></a><strong>Morris遍历细节</strong></h3><p>假设来到当前节点cur，开始时cur来到头节点位置</p>
<ol>
<li><p>如果cur没有左孩子，cur向右移动(cur = cur.right)</p>
</li>
<li><p>如果cur有左孩子，找到左子树上最右的节点mostRight</p>
<ol>
<li><p>如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left)</p>
</li>
<li><p>如果mostRight的右指针指向cur，让其指向null，然后cur向右移动(cur = cur.right)</p>
</li>
</ol>
</li>
<li><p>cur为空时遍历停止</p>
</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">morris</span><span class="params">(Node head)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (head == <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">Node</span> <span class="variable">cur</span> <span class="operator">=</span> head;</span><br><span class="line">    <span class="type">Node</span> <span class="variable">mostRight</span> <span class="operator">=</span> <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">while</span> (cur != <span class="literal">null</span>) &#123;</span><br><span class="line">        mostRight = cur.left;</span><br><span class="line">        <span class="keyword">if</span> (mostRight != <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">while</span> (mostRight.right != <span class="literal">null</span> &amp;&amp; mostRight.right != cur) &#123;</span><br><span class="line">                mostRight = mostRight.right;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (mostRight.right == <span class="literal">null</span>) &#123;</span><br><span class="line">                mostRight.right = cur;</span><br><span class="line">                cur = cur.left;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                mostRight.right = <span class="literal">null</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        cur = cur.right;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="Morris遍历之先序遍历"><a href="#Morris遍历之先序遍历" class="headerlink" title="Morris遍历之先序遍历"></a><strong>Morris遍历之先序遍历</strong></h3><p>如果一个节点只到达一次，直接打印</p>
<p>如果一个节点能够到达两次，第一次打印</p>
<figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">morrisPre</span>(<span class="params">Node head</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (head == <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Node cur = head;</span><br><span class="line">    Node mostRight = <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">while</span> (cur != <span class="literal">null</span>) &#123;</span><br><span class="line">        mostRight = cur.left;</span><br><span class="line">        <span class="keyword">if</span> (mostRight != <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">while</span> (mostRight.right != <span class="literal">null</span> &amp;&amp; mostRight.right != cur) &#123;</span><br><span class="line">                mostRight = mostRight.right;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (mostRight.right == <span class="literal">null</span>) &#123;<span class="comment">//这是第一次来到这个节点</span></span><br><span class="line">                System.<span class="keyword">out</span>.print(cur.<span class="keyword">value</span> + <span class="string">&quot; &quot;</span>);</span><br><span class="line">                mostRight.right = cur;</span><br><span class="line">                cur = cur.left;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;<span class="comment">//第二次来到这个节点</span></span><br><span class="line">                mostRight.right = <span class="literal">null</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;<span class="comment">//没有左子树的情况</span></span><br><span class="line">            System.<span class="keyword">out</span>.print(cur.<span class="keyword">value</span> + <span class="string">&quot; &quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        cur = cur.right;</span><br><span class="line">    &#125;</span><br><span class="line">    System.<span class="keyword">out</span>.println();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="Morris遍历之中序遍历"><a href="#Morris遍历之中序遍历" class="headerlink" title="Morris遍历之中序遍历"></a><strong>Morris遍历之中序遍历</strong></h3><p>如果一个节点只到达一次，直接打印</p>
<p>如果一个节点能够到达两次，第二次打印<br><figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">morrisIn</span>(<span class="params">Node head</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (head == <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Node cur = head;</span><br><span class="line">    Node mostRight = <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">while</span> (cur != <span class="literal">null</span>) &#123;</span><br><span class="line">        mostRight = cur.left;</span><br><span class="line">        <span class="keyword">if</span> (mostRight != <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">while</span> (mostRight.right != <span class="literal">null</span> &amp;&amp; mostRight.right != cur) &#123;</span><br><span class="line">                mostRight = mostRight.right;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (mostRight.right == <span class="literal">null</span>) &#123;</span><br><span class="line">                mostRight.right = cur;</span><br><span class="line">                cur = cur.left;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                mostRight.right = <span class="literal">null</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        System.<span class="keyword">out</span>.print(cur.<span class="keyword">value</span> + <span class="string">&quot; &quot;</span>);</span><br><span class="line">        cur = cur.right;</span><br><span class="line">    &#125;</span><br><span class="line">    System.<span class="keyword">out</span>.println();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="Morris遍历之后序遍历"><a href="#Morris遍历之后序遍历" class="headerlink" title="Morris遍历之后序遍历"></a><strong>Morris遍历之后序遍历</strong></h3><figure class="highlight typescript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="built_in">void</span> <span class="title function_">morrisPos</span>(<span class="params">Node head</span>) &#123;</span><br><span class="line">    <span class="keyword">if</span> (head == <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="title class_">Node</span> cur = head;</span><br><span class="line">    <span class="title class_">Node</span> mostRight = <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">while</span> (cur != <span class="literal">null</span>) &#123;</span><br><span class="line">        mostRight = cur.<span class="property">left</span>;</span><br><span class="line">        <span class="keyword">if</span> (mostRight != <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">while</span> (mostRight.<span class="property">right</span> != <span class="literal">null</span> &amp;&amp; mostRight.<span class="property">right</span> != cur) &#123;</span><br><span class="line">                mostRight = mostRight.<span class="property">right</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (mostRight.<span class="property">right</span> == <span class="literal">null</span>) &#123;</span><br><span class="line">                mostRight.<span class="property">right</span> = cur;</span><br><span class="line">                cur = cur.<span class="property">left</span>;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                mostRight.<span class="property">right</span> = <span class="literal">null</span>;</span><br><span class="line">                <span class="title function_">printEdge</span>(cur.<span class="property">left</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        cur = cur.<span class="property">right</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="title function_">printEdge</span>(head);</span><br><span class="line">    <span class="title class_">System</span>.<span class="property">out</span>.<span class="title function_">println</span>();</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="built_in">void</span> <span class="title function_">printEdge</span>(<span class="params">Node head</span>) &#123;</span><br><span class="line">    <span class="title class_">Node</span> tail = <span class="title function_">reverseEdge</span>(head);</span><br><span class="line">    <span class="title class_">Node</span> cur = tail;</span><br><span class="line">    <span class="keyword">while</span> (cur != <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="title class_">System</span>.<span class="property">out</span>.<span class="title function_">print</span>(cur.<span class="property">value</span> + <span class="string">&quot; &quot;</span>);</span><br><span class="line">        cur = cur.<span class="property">right</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="title function_">reverseEdge</span>(tail);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="title class_">Node</span> <span class="title function_">reverseEdge</span>(<span class="params">Node <span class="keyword">from</span></span>) &#123;</span><br><span class="line">    <span class="title class_">Node</span> pre = <span class="literal">null</span>;</span><br><span class="line">    <span class="title class_">Node</span> next = <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">while</span> (<span class="keyword">from</span> != <span class="literal">null</span>) &#123;</span><br><span class="line">        next = <span class="keyword">from</span>.<span class="property">right</span>;</span><br><span class="line">        <span class="keyword">from</span>.<span class="property">right</span> = pre;</span><br><span class="line">        pre = <span class="keyword">from</span>;</span><br><span class="line">        <span class="keyword">from</span> = next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pre;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="大数据题目的解题技巧"><a href="#大数据题目的解题技巧" class="headerlink" title="大数据题目的解题技巧"></a><strong>大数据题目的解题技巧</strong></h2><ol>
<li><p>哈希函数可以把数据按照种类分流</p>
</li>
<li><p>布隆过滤器用于集合的建立与查询，并可以节省大量空间</p>
</li>
<li><p>一致性哈希解决数据服务器的负载管理问题</p>
</li>
<li><p>利用并查集结构做岛问题的并行计算</p>
</li>
<li><p>位图(用一个比特就能表示一个数出现或者没出现过)解决某一范围上数字的出现情况，并可以节省大量空间</p>
</li>
<li><p>利用分段思想、并进一步节省大量空间</p>
</li>
<li><p>利用堆、外排序来做多个处理单元的结果合并</p>
</li>
</ol>
<h2 id="位图解决类型的题目"><a href="#位图解决类型的题目" class="headerlink" title="位图解决类型的题目"></a><strong>位图解决类型的题目</strong></h2><p>32位无符号整数的范围是0~4294967295(2^32-1),现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数？</p>
<p>【进阶】内存限制位为10MB，但是只用找到一个没出现过的数即可</p>
<p>【再进阶】假如只能申请几个有限变量，怎么找到一个没出现过的数</p>
<p>分段</p>
<hr>
<p>有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL</p>
<p>【补充】某搜索公司一天的用户搜索词汇是海量的，请设计一种求出每天热门Top100词汇的可行方法</p>
<p>布隆过滤器、哈希分流</p>
<p>大根堆实现补充的问题</p>
<h2 id="题目分类"><a href="#题目分类" class="headerlink" title="题目分类"></a><strong>题目分类</strong></h2><ol>
<li><p>业务为主的题目</p>
<ul>
<li>业务为主的题目，主要核心思想是它业务本身，根据业务逻辑做出算法逻辑</li>
</ul>
</li>
<li><p>技巧为主的题目</p>
<ul>
<li>业务对最后的算法思想不是多重要，反而是你已经熟悉的技巧比如红黑树等成熟的数据结构，对最后算法起到根本作用。</li>
</ul>
</li>
</ol>
<p>笔试阶段：</p>
<p>业务为主的题会占到55%，技巧为主的题会占到45%</p>
<p>面试阶段：</p>
<p>业务为主的题会占到30%，技巧为主的题会占到70%</p>
<h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a><strong>堆排序</strong></h2><h3 id="heapInsert"><a href="#heapInsert" class="headerlink" title="heapInsert"></a><strong>heapInsert</strong></h3><figure class="highlight axapta"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> heapInsert(<span class="built_in">int</span>[] arr,<span class="built_in">int</span> <span class="keyword">index</span>)&#123;</span><br><span class="line">    <span class="keyword">while</span>(arr[<span class="keyword">index</span>] &gt; arr[(<span class="keyword">index</span><span class="number">-1</span>)/<span class="number">2</span>])&#123;</span><br><span class="line">        swap(arr,<span class="keyword">index</span>,(<span class="keyword">index</span><span class="number">-1</span>)/<span class="number">2</span>);</span><br><span class="line">        <span class="keyword">index</span> = (<span class="keyword">index</span><span class="number">-1</span>)/<span class="number">2</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="heapify"><a href="#heapify" class="headerlink" title="heapify"></a><strong>heapify</strong></h3><figure class="highlight axapta"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> heapify(<span class="built_in">int</span>[] arr,<span class="built_in">int</span> <span class="keyword">index</span>,<span class="built_in">int</span> heapSize)&#123;</span><br><span class="line">    <span class="built_in">int</span> left = <span class="keyword">index</span>*<span class="number">2</span> + <span class="number">1</span>;<span class="comment">//左孩子的下标</span></span><br><span class="line">    <span class="keyword">while</span>(left &lt; heapSize)&#123;<span class="comment">//下方还有孩子的时候</span></span><br><span class="line">        <span class="comment">//两个孩子中，谁的值大，把下标给largest</span></span><br><span class="line">        <span class="built_in">int</span> largest = left+<span class="number">1</span> &lt; heapSize &amp;&amp; arr[left+<span class="number">1</span>] &gt; arr[left] ? left + <span class="number">1</span> : left;</span><br><span class="line">        <span class="comment">//父和孩子之间，谁的值大，把下标给largest</span></span><br><span class="line">        largest = arr[largest] &gt; arr[<span class="keyword">index</span>] ? largest : <span class="keyword">index</span>;</span><br><span class="line">        <span class="keyword">if</span>(largest == <span class="keyword">index</span>)&#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        swap(arr,largest,<span class="keyword">index</span>);</span><br><span class="line">        <span class="keyword">index</span> = largest;</span><br><span class="line">        left = <span class="keyword">index</span> * <span class="number">2</span> + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> swap(<span class="built_in">int</span>[] arr,<span class="built_in">int</span> i,<span class="built_in">int</span> j)&#123;</span><br><span class="line">    <span class="built_in">int</span> temp = arr[i];</span><br><span class="line">    arr[i] = arr[j];</span><br><span class="line">    arr[j] = arr[i];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="两个栈拼出一个队列和两个队列拼出一个栈"><a href="#两个栈拼出一个队列和两个队列拼出一个栈" class="headerlink" title="两个栈拼出一个队列和两个队列拼出一个栈"></a><strong>两个栈拼出一个队列和两个队列拼出一个栈</strong></h2><p>图的深度优先遍历，让你用队列做————两个栈拼一个队列</p>
<p>图的宽度优先遍历，让你用栈做————两个栈拼一个队列</p>
<h2 id="动态规划的空间压缩技巧"><a href="#动态规划的空间压缩技巧" class="headerlink" title="动态规划的空间压缩技巧"></a><strong>动态规划的空间压缩技巧</strong></h2><p>给你一个二维数组matrix，其中每个数都是正数，要求从左上角走到右下角。每一步只能向右或者向下，沿途经过的数字要累加起来。最后请返回最小的路径和。</p>
<h2 id="给定一个数组arr，如果通过调整可以做到arr中任意两个相邻的数组相乘是4的倍数，返回true，如果不能返回false"><a href="#给定一个数组arr，如果通过调整可以做到arr中任意两个相邻的数组相乘是4的倍数，返回true，如果不能返回false" class="headerlink" title="给定一个数组arr，如果通过调整可以做到arr中任意两个相邻的数组相乘是4的倍数，返回true，如果不能返回false"></a><strong>给定一个数组arr，如果通过调整可以做到arr中任意两个相邻的数组相乘是4的倍数，返回true，如果不能返回false</strong></h2><p>遍历数组，统计三类数的个数</p>
<ol>
<li><p>奇数 a个</p>
</li>
<li><p>偶数</p>
<ul>
<li><p>只含有一个2因子的数 b个</p>
</li>
<li><p>包含4因子的数 c个</p>
</li>
</ul>
</li>
</ol>
<p>第一种情况，b == 0时， </p>
<pre><code>+ 如果a = 1，c &gt;= 1
+ 如果a &gt; 1，c &gt;= a-1
</code></pre><p>第二种情况，b != 0时，先把b类数摆在一起，</p>
<pre><code>+ 如果a = 0，c &gt;= 0
+ 如果a = 1,c &gt;= 1
+ 如果a &gt; 1,c &gt;= a
</code></pre>
    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/wang-cheng/tags/%E5%B7%A6%E7%A5%9E/" rel="tag"># 左神</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E5%9B%9B/" rel="prev" title="算法笔记(四)">
      <i class="fa fa-chevron-left"></i> 算法笔记(四)
    </a></div>
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/04/10/%E5%A4%9A%E7%BA%BF%E7%A8%8B/" rel="next" title="多线程">
      多线程 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A0%91%E5%BD%A2dp%E5%A5%97%E8%B7%AF"><span class="nav-number">1.</span> <span class="nav-text">树形dp套路</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Morris%E9%81%8D%E5%8E%86"><span class="nav-number">2.</span> <span class="nav-text">Morris遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Morris%E9%81%8D%E5%8E%86%E7%BB%86%E8%8A%82"><span class="nav-number">2.1.</span> <span class="nav-text">Morris遍历细节</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Morris%E9%81%8D%E5%8E%86%E4%B9%8B%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86"><span class="nav-number">2.2.</span> <span class="nav-text">Morris遍历之先序遍历</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Morris%E9%81%8D%E5%8E%86%E4%B9%8B%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86"><span class="nav-number">2.3.</span> <span class="nav-text">Morris遍历之中序遍历</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Morris%E9%81%8D%E5%8E%86%E4%B9%8B%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86"><span class="nav-number">2.4.</span> <span class="nav-text">Morris遍历之后序遍历</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A4%A7%E6%95%B0%E6%8D%AE%E9%A2%98%E7%9B%AE%E7%9A%84%E8%A7%A3%E9%A2%98%E6%8A%80%E5%B7%A7"><span class="nav-number">3.</span> <span class="nav-text">大数据题目的解题技巧</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BD%8D%E5%9B%BE%E8%A7%A3%E5%86%B3%E7%B1%BB%E5%9E%8B%E7%9A%84%E9%A2%98%E7%9B%AE"><span class="nav-number">4.</span> <span class="nav-text">位图解决类型的题目</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E5%88%86%E7%B1%BB"><span class="nav-number">5.</span> <span class="nav-text">题目分类</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A0%86%E6%8E%92%E5%BA%8F"><span class="nav-number">6.</span> <span class="nav-text">堆排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#heapInsert"><span class="nav-number">6.1.</span> <span class="nav-text">heapInsert</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#heapify"><span class="nav-number">6.2.</span> <span class="nav-text">heapify</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%A4%E4%B8%AA%E6%A0%88%E6%8B%BC%E5%87%BA%E4%B8%80%E4%B8%AA%E9%98%9F%E5%88%97%E5%92%8C%E4%B8%A4%E4%B8%AA%E9%98%9F%E5%88%97%E6%8B%BC%E5%87%BA%E4%B8%80%E4%B8%AA%E6%A0%88"><span class="nav-number">7.</span> <span class="nav-text">两个栈拼出一个队列和两个队列拼出一个栈</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9A%84%E7%A9%BA%E9%97%B4%E5%8E%8B%E7%BC%A9%E6%8A%80%E5%B7%A7"><span class="nav-number">8.</span> <span class="nav-text">动态规划的空间压缩技巧</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E6%95%B0%E7%BB%84arr%EF%BC%8C%E5%A6%82%E6%9E%9C%E9%80%9A%E8%BF%87%E8%B0%83%E6%95%B4%E5%8F%AF%E4%BB%A5%E5%81%9A%E5%88%B0arr%E4%B8%AD%E4%BB%BB%E6%84%8F%E4%B8%A4%E4%B8%AA%E7%9B%B8%E9%82%BB%E7%9A%84%E6%95%B0%E7%BB%84%E7%9B%B8%E4%B9%98%E6%98%AF4%E7%9A%84%E5%80%8D%E6%95%B0%EF%BC%8C%E8%BF%94%E5%9B%9Etrue%EF%BC%8C%E5%A6%82%E6%9E%9C%E4%B8%8D%E8%83%BD%E8%BF%94%E5%9B%9Efalse"><span class="nav-number">9.</span> <span class="nav-text">给定一个数组arr，如果通过调整可以做到arr中任意两个相邻的数组相乘是4的倍数，返回true，如果不能返回false</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">王诚</p>
  <div class="site-description" itemprop="description">命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/wang-cheng/archives/">
        
          <span class="site-state-item-count">32</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/wang-cheng/tags/">
          
        <span class="site-state-item-count">12</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">王诚</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/wang-cheng/lib/anime.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.ui.min.js"></script>

<script src="/wang-cheng/js/utils.js"></script>

<script src="/wang-cheng/js/motion.js"></script>


<script src="/wang-cheng/js/schemes/pisces.js"></script>


<script src="/wang-cheng/js/next-boot.js"></script>




  















  

  
      

<script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      loader: {
        source: {
          '[tex]/amsCd': '[tex]/amscd',
          '[tex]/AMScd': '[tex]/amscd'
        }
      },
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              let target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    (function () {
      var script = document.createElement('script');
      script.src = '//cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js';
      script.defer = true;
      document.head.appendChild(script);
    })();
  } else {
    MathJax.startup.document.state(0);
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  

</body>
</html>
